// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
var hIndex1 = function(citations) {
    let left = 0, right = citations.length;
    while (left < right) {
        let mid = left + Math.floor((right - left + 1) / 2);

        let cnt = 0;
        for (let i = 0; i < citations.length; i++) {
            if (citations[i] >= mid) cnt++;
        }

        if (cnt >= mid) left = mid;
        else right = mid - 1;
    }
    return left;
};

var hIndex2 = function(citations) {
    citations.sort((a, b) => a - b);
    let n = citations.length;
    for (let h = n; h > 0; h--) {
        if (citations[n - h] >= h) return h;
    }
    return 0;
};


var hIndex3 = function(citations) {
    citations.sort((a, b) => a - b);
    const n = citations.length;
    let left = 0,
        right = n;
    while (left < right) {
        const h = left + Math.floor((right - left + 1) / 2);
        if (citations[n - h] >= h) {
            left = h;
        } else {
            right = h - 1;
        }
    }
    return left;
};

var hIndex = function(citations) {
    const n = citations.length;
    const counter = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        if (citations[i] >= n) {
            counter[n]++;
        } else {
            counter[citations[i]]++;
        }
    }

    let total = 0;
    for (let h = n; h >= 0; h--) {
        total += counter[h];
        if (total >= h) {
            return h;
        }
    }

    return 0;
};